#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include"assert.h"

///a common and short writting of gcd.
int gcd(int less,int greater)
{
    while(less!=0)
    {
        int temp=greater%less;
        greater=less;
        less=temp;
    }
}

int biggestCommon(int x,int y)
{
    if(x>y)
    {
        x=x^y^x;
        y=x^y;
    }

    if(x==0)
    return y;

    return biggestCommon(y%x,x);
}

bool gradSortAndCheck(int arr[],int length,int grade)
{
    for(int i=0;i<grade;i++)
    {
        for(int j=i+grade;j<length;j+=grade)
        {
            int k=j;
            while((k-grade)>=0 && arr[k]<arr[k-grade])
            {
                int temp=arr[k-grade];
                arr[k-grade]=arr[k];
                arr[k]=temp;

                k=k-grade;
            }
        }
    }

    for(int i=0;i<length;i++)
        printf("%d ",arr[i]);
    printf("\n");

    for(int i=0;i<length-1;i++)
    {
        if(arr[i]>arr[i+1]) return false;
    }
    return true;
}

int main()
{
    assert(biggestCommon(1,3)==1);
    assert(biggestCommon(2,6)==2);
    assert(biggestCommon(3,3333333)==3);

    int a[]={1,3,5,8,3,2,9,4};
    gradSortAndCheck(a,8,biggestCommon(2,8));
}
